package com.harvey.study.data.structure.datastructure.linkedlist;

/**
 * date: 2021-04-22
 * desc: 循环链表 尾节点为特殊节点指向首节点
 */
public class LoopLinkedList<T> {
    private Node<T> lastNode; //尾节点,添加目的两个链表拼接的时候无需循环拿最后一个节点，减少时间复杂度
    private Node<T> rear; //指向头节点
    private int length;
    
    public LoopLinkedList() {
        rear = new Node<>();
    }
    
    public boolean add(T data,int pos){
        checkPos(pos);
        int index = 1;
        Node<T> p = rear;
        Node<T> q = p.next;
        while(index++<pos){
            p = q;
            q = q.next;
        }
        p.next = new Node<T>(data,pos==1?rear:q);
        length++;
        if(length == pos){
            lastNode = p.next;
        }
        return true;
    }

    public boolean add(T data){
        return add(data,length+1);
    }

    public boolean remove(int pos){
        checkPos(pos);
        if(isEmpty()){
            return true;
        }
        int index = 1;
        Node<T> p = rear;
        Node<T> q = p.next;
        while(index++<pos){
            p = q;
            q = q.next;
        }
        if(pos == length){
            lastNode = p;
        }
        length--;
        p.next = isEmpty()?new Node<>():q.next;
        return true;
    }

    public int remove(T data){
        if(isEmpty()){
            return -1;
        }
        int index = 1;
        Node<T> p = rear;
        Node<T> q = p.next;
        while(index++<length){
            if(q.data.equals(data)){
                break;
            }
            p = q;
            q = q.next;
        }
        if(index == length){
            lastNode = p;
        }
        length--;
        p.next = isEmpty()?new Node<>():q.next;
        return index;
    }

    public void clear(){
        length = 0;
        rear = new Node<>();
        lastNode = null;
    }


    public boolean modify(T data,int pos){
        checkPos(pos);
        int index = 1;
        Node<T> p = rear.next;
        while(index++<pos){
            p = p.next;
        }
        p.data = data;
        return true;
    }


    public int find(T data){
        if(isEmpty()){
            return -1;
        }
        int index = 1;
        Node<T> head = rear.next;
        while(index++<=length){
            if(head.data.equals(data)){
                break;
            }
            head = head.next;
        }
        return index;
    }

    public T value(int pos){
        checkPos(pos);
        if(isEmpty()){
            return null;
        }
        int index = 1;
        Node<T> head = rear.next;
        while(index++<pos){
            head = head.next;
        }
        return head.data;
    }

    public Node<T> findNode(int pos){
        checkPos(pos);
        if(isEmpty()){
            return null;
        }
        int index = 1;
        Node<T> head = rear.next;
        while(index++<pos){
            head = head.next;
        }
        return head;
    }

    public boolean addAll(LoopLinkedList<T> linkedList){
        if(linkedList.isEmpty()){
            return true;
        }
        lastNode.next = linkedList.rear.next;
        linkedList.rear.next = rear.next;
        rear = linkedList.rear;
        lastNode = linkedList.lastNode;
        length+=linkedList.size();
        return true;
    }

    public boolean isEmpty(){
        return length==0;
    }

    public int size(){
        return length;
    }

    private void checkPos(int pos){
        if(pos<1 || pos>length+1){
            throw new RuntimeException("pos不合法");
        }
    }

    public static void main(String[] args) {
        LoopLinkedList<String> list = new LoopLinkedList<>();
        list.add("a",1);
        list.add("b",2);




        LoopLinkedList<String> loopLinkedList = new LoopLinkedList<>();
        loopLinkedList.add("1",1);
        loopLinkedList.add("2",2);
        loopLinkedList.add("3",3);
        loopLinkedList.add("4",4);
        loopLinkedList.add("5",5);
        list.addAll(loopLinkedList);

        // list.remove(5);

        // LoopLinkedList<String> loopLinkedList1 = new LoopLinkedList<>();
        // loopLinkedList1.add("1",1);
        // loopLinkedList1.add("2",2);
        // loopLinkedList1.add("3",3);
        // loopLinkedList1.add("4",4);
        // loopLinkedList1.add("5",5);
        // list.addAll(loopLinkedList1);


        Node<String> head = list.rear.next;
        while(head.data!=null){
            System.out.println(head.data);
            head = head.next;
        }

        // System.out.println(loopLinkedList.value(10));
        // System.out.println(loopLinkedList.find("10"));
    }

}
